package 数据结构.算法;

import java.util.Arrays;
import java.util.Scanner;
public class KMP算法 {

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        System.out.println("请输入主串T：");
        String T=input.nextLine();
        System.out.println("请输入模式串S：");
        String S=input.nextLine();
        //数组的内容都从1开始存储，不用0号元素方便实现
        char []a=new char[T.length()+1];int next[]=new int[S.length()+1];
        char []b=new char[S.length()+1];int i=1,j=1;
        for (char x:T.toCharArray()//将字符串T中的数据逐个的放入到字符数组中
        ) {
            a[i]=x;i++;
        }
        for (char m:S.toCharArray()//将字符串S中的数据逐个的放入到字符数组中
             ) {
            b[j]=m;j++;
        }
        //get_next(b,next);//获得next数组
        //System.out.println("next: "+Arrays.toString(next));
        get_nextval(b,next);//获得nextval数组即next数组的改良版
        //System.out.println("nextval: "+Arrays.toString(next));
        int x=Index_kmp(a,b,next,1);
        System.out.println("从主串的第"+(x-b.length+1)+"项开始达成了匹配！");
    }

    static int Index_kmp(char[] a, char[] b, int[] next, int pos){
        int i=pos,j=1;
        /*
        abcaabbabcabaacbacba
        abcabaa*/
        while (i<=(a.length-1)&&j<=(b.length-1)){
            if(j==0||a[i]==b[j]){
                ++i;++j;
            }else j=next[j];
        }

        if(j>b.length-1)
            return i;
        else
            return -1;
    }
    static void get_next(char[] a, int next[]){
        int i=1;next[1]=0;int j=0;
        while (i<a.length-1){
            if(j==0||a[i]==a[j]){//如果找到匹配或者达到最开始的那个元素，则进行添加想应位置的next值
                i++;j++;next[i]=j;
            }else j=next[j];
        }
    }
    static void get_nextval(char[] a, int nextval[]){
        int i=1;nextval[1]=0;int j=0;
        while (i<a.length-1){
            if(j==0||a[i]==a[j]){
                i++;j++;
                if(a[i]!=a[j])//如果第i为的数据和当前j位置的数相等，那么当前未知的数据就等于J位置的next值
                    nextval[i]=j;
                else
                nextval[i]=nextval[j];
            }else j=nextval[j];
        }
    }
}
/*
abcaabbabcabaacbacba
abcabaa
next 0111232
nextval 0110132
*/